1. Field of the Invention
The present invention relates to methods and apparatuses for accessing data in a memory system, and more particularly, to a method and apparatus for rapidly accessing data in a frame buffer for generating video images on a display panel of a computer system.
Description of the Related Art
A current trend in hardware and software design is the development of computer systems and software applications for processing and displaying video images. Software for processing and displaying video images finds widespread application in user interfaces, plotting software, electronic publishing applications, computer-aided drafting and design programs, computer simulation, animation software, and the like. Many computer systems provide software support for generating, processing and displaying video images in the form of a graphics software package that provides video generation and processing routines available to both hardware, such as a central processing unit (CPU), and also other software applications, such as user interfaces. Such a graphics software package typically implements a recognized graphics specification, such as Direct3D from Microsoft, or OpenGL from Silicon Graphics, for improved portability of software applications into and out of the computer system.
For generating and processing video images, the hardware of a conventional computer system typically includes a central processing unit (CPU) for running software, a system memory for storing software and data for the CPU, one or more input devices such as a keyboard or a mouse, a display panel having a display surface containing an array of picture elements (pixels) with the intensity and color of each pixel being separately controllable for generating video images, a frame buffer for storing data that identifies the proper intensity and color to be provided by each pixel of the display surface (herein video data), a video controller for reading video data in the frame buffer and sending the video data to the display panel in an appropriate format for controlling the pixels, and a bus for carrying digital data such as the video data among various components of the computer system. Many conventional computer systems additionally include a display processor that supplements the CPU at generating and processing video images.
Many conventional computer systems use a cathode ray tube monitor (CRT monitor) similar to the picture tube of a conventional television set, as a display panel, and the video controller typically converts the video data from the digital format used by the CPU, system memory, frame buffer, bus, and input devices into an appropriate analog format for the CRT monitor, and then sends the analog data to the CRT monitor on a dedicated analog line.
The system memory of conventional computer systems typically comprises a plurality of memory cells. Each memory cell holds a word of data and has a distinct address. The address of a memory cell distinguishes the memory cell from other memory cells in the system memory, and is used for accessing the memory cell to read or write data in the memory cell. The addresses are typically numerical and form a sequence from a low address to a high address in the system memory. To read a word of data from the system memory, the system memory is provided a read request and the address for the memory cell storing the word. Similarly, to write a word of data in the system memory, the system memory is provided a write request, the address of the memory cell that will store the word, and the word of data.
The frame buffer is typically a data storage device similar to the system memory, and in some conventional computer systems, the frame buffer is merely a portion of the system memory. The frame buffer typically holds the video data as a pixel map (pixmap) that associates each pixel of the display panel with a distinct memory cell of the frame buffer that holds a word of video data identifying the intensity and color that the associated pixel should provide. The address of the memory cell storing the video data for a pixel can be determined by the location of the pixel on the display surface. The location of a pixel typically is identified by a horizontal X coordinate and a vertical Y coordinate of the pixel (herein (X, Y) coordinates) on the display surface. The data stored in the frame buffer is appropriately updated to change the image displayed on the display surface.
Because pixmaps can require a large volume of memory storage to implement, conventional computer systems typically store the words of a pixmap at consecutive addresses of the frame buffer to avoid wasting storage capacity in the frame buffer. These consecutive addresses are typically generated using addition and multiplication hardware in the CPU or a display processor when reading or writing video data in the frame buffer and also in the video controller when reading the frame buffer to obtain data to be sent to the display panel. The multiplication and addition operations are applied to the horizontal X coordinate and the vertical Y coordinate of the pixel to determine the address of the pixel. For example, to generate a linear addressing of the frame buffer, a conventional computer system typically multiplies the Y coordinate by the number of pixels in each horizontal line of pixels on the display surface and then adds to the product the X coordinate and a memory offset that determines the first address in the frame buffer. The time needed to perform multiplication and addition operations for generating addresses for video data can delay the generation of video images and the hinder the CPU in performing other operations by tying up the system memory.
Processing video images often requires access by the CPU or display processor to video data associated with localized regions of the display panel as opposed to access to data associated with an isolated pixel or pixels. For example, to generate a wide line for display, a CPU or display processor may need to write video data associated with numerous adjoining pixels of a display panel into the frame buffer. Similarly, filtering of video images may require a CPU or display processor to both read and write data associated with adjoining pixels of the display surface. For providing rapid access to such localized data, some conventional computer systems store pixmaps in a tiled pattern within a frame buffer, with the display surface identified as an array of rectangular tiles with each tile holding a rectangular array of pixels, and with the pixels of each tile stored in a continuous sequence of addresses of the frame buffer.
Unfortunately, conventional computer systems are typically limited in the extent to which they can advantageously implement tiling schemes. Generating tiled addresses often requires a CPU or display processor to perform arithmetic operations that can be more complicated than the multiplication and addition operations used in the linear addressing of the frame buffer described above. Further, a linearly addressed frame buffer is often preferable for conventional video controllers because conventional display panels such as CRT monitors are typically illuminated by scanning pixels on a display surface of the display panel on a horizontal scan line by horizontal scan line manner. However, implementing a tiling pattern with relatively square tiles having the same or approximately the same number of pixels on horizontal sides as vertical sides is often desirable for generating graphics primitives such as circles and lines of various widths. Balancing the desirability of relatively square tiles with these limitations of conventional CPUs, display processors and video controllers generally results in tiles that are 8 to 32 times as wide as they are high. Further, some software applications generate their own linear addresses for video data in the frame buffer without the support of a graphics package or display processor. Such linear addresses typically are invalid in conventional tiled frame buffers, and a CPU or display processor typically must intercept and correct the invalid linear addresses to properly match the particular tiling employed in the frame buffer. Often, this is implemented using a display processor to convert the linear address back into the corresponding (X,Y) coordinates of the pixel and then to generate the appropriate tiled address from the generated (X,Y) coordinates. Considerable time is needed to perform each of these sequential steps, thus reducing the speed and temporal smoothness of presentation of the associated video image.
Intercepting (X,Y) coordinates and converting them into tiled addresses poses additional technical problems. First, since the (X,Y) coordinates may be stored in scatter gather memory, there may be multiple address ranges, potentially requiring a large number of clocks or multi-clock delay to check memory addresses. Second, converting back to (X,Y) coordinates requires an integer divide by the span size with remainder, which can be time-consuming. Finally, applications may wish to access data directly, which may cause problems if the interception is not transparent to the application.
In general, conversion or remapping from linear addresses to tiled addresses and vice versa can impose significant computational load and diminish performance of the system. Remapping from tiled addresses to linear addresses involves a relatively expensive multiply operation, and remapping from linear to tiled involves an even more expensive divide operation.
There is thus a need for an improved data accessing system that can provide rapid access and updating of pixmaps and other video data stored in one or more frame buffers. Such a data accessing system should preferably provide access to a frame buffer in response to receiving linear addresses, tiled addresses, or (X,Y) pixel coordinates, and should avoid time-consuming arithmetic operations, such as multiply or divide for generating or converting addresses. Such a data accessing system should preferably be able to generate tiled addressing of the frame buffer or buffers from received addresses or (X,Y) pixel coordinates. Such a data accessing system should also store a pixmap without wasting storage capacity in the frame buffer. Preferably such a system should also support a standard graphics specification such as Direct3D or OpenGL for generating detailed and dynamic graphic images, and for allowing the use of graphics applications designed in conformance with the standard graphics specification.